;;;; sort.test --- tests Guile's sort functions    -*- scheme -*-
;;;; Copyright (C) 2003, 2006, 2007 Free Software Foundation, Inc.
;;;; 
;;;; This program is free software; you can redistribute it and/or modify
;;;; it under the terms of the GNU General Public License as published by
;;;; the Free Software Foundation; either version 2, or (at your option)
;;;; any later version.
;;;; 
;;;; This program is distributed in the hope that it will be useful,
;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;;; GNU General Public License for more details.
;;;; 
;;;; You should have received a copy of the GNU General Public License
;;;; along with this software; see the file COPYING.  If not, write to
;;;; the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
;;;; Boston, MA 02110-1301 USA

(use-modules (test-suite lib))

(define (randomize-vector! v n)
  (array-index-map! v (lambda (i) (random n)))
  v)

(with-test-prefix "sort"

  (pass-if-exception "less function taking less than two arguments"
    exception:wrong-type-arg
    (sort '(1 2) (lambda (x) #t)))

  (pass-if-exception "less function taking more than two arguments"
    exception:wrong-type-arg
    (sort '(1 2) (lambda (x y z) z)))

  (pass-if "sort!"
    (let ((v (randomize-vector! (make-vector 1000) 1000)))
      (sorted? (sort! v <) <)))

  (pass-if "sort! of non-contigous vector"
    (let* ((a (make-array 0 1000 3))
	   (v (make-shared-array a (lambda (i) (list i 0)) 1000)))
      (randomize-vector! v 1000)
      (sorted? (sort! v <) <)))

  (pass-if "sort! of negative-increment vector"
    (let* ((a (make-array 0 1000 3))
	   (v (make-shared-array a (lambda (i) (list (- 999 i) 0)) 1000)))
      (randomize-vector! v 1000)
      (sorted? (sort! v <) <)))

  (pass-if "stable-sort!"
    (let ((v (randomize-vector! (make-vector 1000) 1000)))
      (sorted? (stable-sort! v <) <)))

  (pass-if "stable-sort! of non-contigous vector"
    (let* ((a (make-array 0 1000 3))
	   (v (make-shared-array a (lambda (i) (list i 0)) 1000)))
      (randomize-vector! v 1000)
      (sorted? (stable-sort! v <) <)))

  (pass-if "stable-sort! of negative-increment vector"
    (let* ((a (make-array 0 1000 3))
	   (v (make-shared-array a (lambda (i) (list (- 999 i) 0)) 1000)))
      (randomize-vector! v 1000)
      (sorted? (stable-sort! v <) <))))


;;;
;;; stable-sort
;;;

(with-test-prefix "stable-sort"

  ;; in guile 1.8.0 and 1.8.1 this test failed, an empty list provoked a
  ;; wrong-type-arg exception (where it shouldn't)
  (pass-if "empty list"
    (eq? '() (stable-sort '() <))))

